package com.study.algorithm.search;

import java.util.Stack;

public class DFS {
    public static void dfs(BinTree tree) {
        if (tree != null) {
            System.out.println("tree = " + tree.getData());
            dfs(tree.getLeft());
            dfs(tree.getRight());
        }
    }

    public static void dfsWithStack(BinTree tree) {
        Stack<BinTree> stack = new Stack<>();
        stack.push(tree);
        while (!stack.isEmpty()) {
            BinTree pop = stack.pop();
            if (pop != null) {
                stack.push(pop.getRight());
                stack.push(pop.getLeft());
                System.out.println("pop = " + pop.getData());
            }
        }
    }

    public static void main(String[] args) {
        /**
         *      1
         *   2     3
         * 4  5   6  7
         */
        BinTree tree4 = new BinTree(4);
        BinTree tree5 = new BinTree(5);
        BinTree tree6 = new BinTree(6);
        BinTree tree7 = new BinTree(7);
        BinTree tree3 = new BinTree(3, tree6, tree7);
        BinTree tree2 = new BinTree(2, tree4, tree5);
        BinTree tree1 = new BinTree(1, tree2, tree3);
        dfsWithStack(tree1);
    }
}
